import random

import pysnooper


def _sort(a, left, right):
    l = left
    r = right
    tmp = a[l]

    while l < r:
        while l < r and tmp <= a[r]:
            r -= 1
        if l < r:
            a[l] = a[r]
            l += 1

        while l < r and a[l] <= tmp:
            l += 1
        if l < r:
            a[r] = a[l]
            r -= 1

    a[l] = tmp

    if left < l - 1:
        _sort(a, left, l - 1)

    if l + 1 < right:
        _sort(a, l + 1, right)


def quickSort(a, N):
    _sort(a, 0, N - 1)


def main():
    a = list()
    for i in range(10):
        a.append(int(random.random() * 100))

    # 结果示例
    # D:\Python39\python.exe D:/workspace_Python/iLearning/Python/Algorithm/QuickSort.py
    # Source path:... D:\workspace_Python\iLearning\Python\Algorithm\QuickSort.py
    # New var:....... a = [99, 80, 41, 89, 30, 54, 89, 6, 59, 76]
    # New var:....... i = 9
    # 17:27:38.037029 line        43         quickSort(a, len(a))
    # Modified var:.. a = [6, 30, 41, 54, 59, 76, 80, 89, 89, 99]
    # 17:27:38.037029 line        45         pass
    # Elapsed time: 00:00:00.000000
    #
    # Process finished with exit code 0
    with pysnooper.snoop():  # 参考https://pypi.org/project/PySnooper/
        quickSort(a, len(a))
        pass  # 注：为了通过pysnooper看变量


if __name__ == '__main__':
    main()
